Оптимизационные задачи на графах
Потоки в сети. Паросочетания. Задача о назначениях
ОГЛАВЛЕНИЕ
1 Введение в тему .............................................................................................................. 3
2 Основные определения .................................................................................................. 4
2.1 Граф ........................................................................................................................... 4
2.2 Ориентированный граф ........................................................................................... 5
2.3 Матрица смежности ................................................................................................. 6
3 Сети и потоки .................................................................................................................. 7
3.1 Сети ........................................................................................................................... 7
3.2 Потоки ....................................................................................................................... 8
3.3 Задача о максимальном потоке в сети ................................................................. 10
3.4 Разрезы .................................................................................................................... 12
4 Нахождение максимального потока и определение минимального разреза .......... 15
4.1 Алгоритм нахождения максимального потока ................................................... 15
4.2 Алгоритм нахождения минимального разреза ................................................... 16
4.3 Особенности алгоритма Форда-Фалкерсона ....................................................... 17
4.4 Пример применения алгоритма Форда-Фалкерсона .......................................... 17
4.5 Максимальность потока, найденного алгоритмом Форда-Фалкерсона ........... 31
5 Связанные задачи .......................................................................................................... 33
5.1 Задача о максимальном потоке минимальной стоимости ................................. 33
5.2 Задача о наибольшем паросочетании в двудольном графе ............................... 35
5.3 Задача о совершенных паросочетаниях ............................................................... 37
6 Паросочетания .............................................................................................................. 39
7 Задача о максимальном паросочетании ...................................................................... 42
7. 1 Общая постановка задачи .................................................................................... 42
7.2 Постановка задачи для двудольных графов ........................................................ 42
2
7.3 Сведение задачи к задаче о максимальном потоке в сети ................................. 42
7.4 Алгоритм Куна решения задачи на двудольных графах ................................... 44
7.5 Алгоритм Эдмондса решения задачи на произвольных графах ....................... 48
8 Задача о совершенном паросочетании ....................................................................... 53
8.1 Общая постановка задачи ..................................................................................... 53
8.2 Постановка задачи для двудольных графов ........................................................ 54
8.3 Задача о назначениях ............................................................................................. 55
8.4 Венгерский алгоритм решения задачи о назначениях ....................................... 58
Список литературы .......................................................................................................... 65
3
1 Введение в тему
Ниже нами будет рассмотрено несколько оптимизационных задач теории графов.
Среди них:
1. задача о максимальном потоке,
2. задача о минимальном разрезе,
3. задача о максимальном паросочетании в графе,
4. задача о назначениях.
Эти задачи тесно связаны между собой и также имеют связь с другими задачами
теории графов. Перечисленные задачи – одни из классических задач теории графов. Они
имеют широкое применение и используются в том числе и при решении других
оптимизационных задач.
Перед тем, как приступить к основному содержанию, определимся с общими
понятиями и обозначениями, которые будут использоваться при дальнейшем изложении
материала.
2 Основные определения
2.1 Граф
Определение 2.1. Неориентированный граф (граф, простой граф) – это
пара множеств, где
– множество вершин и
–
множество рёбер, где
- неупорядоченная пара вершин из V:
.
В обычном графе рёбра не имеют направления (ориентации), а значит, не важен и
порядок написания вершин при их обозначении. Чтобы подчеркнуть это, при обозначении
будем использовать фигурные скобки:
. Как известно, именно
фигурными скобками в математике принято обозначать множества, порядок элементов в
которых также неважен.
Пример графа приведён на рисунке 2.1.
Рисунок 2.1 – Граф
Определение 2.2. Две вершины
и
называют смежными, если между ними
существует ребро
. При этом говорят, что ребро
инцидентно вершинам
и
.
Например, для графа на рисунке 2.1 вершине смежны вершины и , и
инцидентны рёбра и .
Определение 2.3. Путь (маршрут) – это последовательность рёбер, объединённых
вместе вершинами так, что вдоль них можно двигаться по графу. Путь, в котором все
рёбра между смежными вершинами различны, называют цепью. Путь, в котором
,
называется циклом. Обозначать путь будем последовательностью вершин
,
через которые он проходит.
5
Например, для графа на рисунке 2.1 можно составить такие пути: ;
; и т.д. Все перечисленные пути также являются цепями. Циклом, к
примеру, будет путь .
Определение 2.4. Граф называется связным, если из любой его вершины
существует путь в любую другую его вершину.
Таким образом, граф на рисунке 2.1 – связный.
Определение 2.5. Петля – это ребро
, соединяющее вершину с собой же:
.
Одним из видов графов является ориентированный граф.
2.2 Ориентированный граф
Определение 2.6. Ориентированный граф (орграф) – это граф
, рёбра которого имеют направление.
Рёбра орграфа называются дугами. Задаются дуги упорядоченными парами
вершин:
. Поэтому дуги
и
– это разные дуги,
ведущие в противоположных направлениях.
Пример орграфа приведён на рисунке 2.2.
Рисунок 2.2 – Орграф
Определение 2.7. Орграф называется связным, если его соотнесённый граф ,
полученный из исходного забыванием ориентации дуг, является связным.
6
2.3 Матрица смежности
Определение 2.8. Матрица смежности A графа G – это квадратная матрица
размерности , где – количество вершин графа. Строки и столбцы матрицы
соответствуют вершинам графа. Матрица имеет следующий вид:
Матрица состоит из нулей и единиц, и каждый элемент матрицы вычисляется по
следующему правилу:
Если граф взвешенный (каждому ребру графа поставлена в соответствие некоторая
величина – вес ребра), то
, где
– вес ребра между вершинами
и
.
При дальнейшем рассмотрении орграфов нам понадобится находить вершины,
смежные с конкретной вершиной. Введём для этого следующие обозначения.
Обозначим через
множество вершин, смежных с вершиной :
.
Вершины, из которых в вершину есть дуга, будем обозначать как
:
.
3 Сети и потоки
3.1 Сети
Задача о максимальном потоке и задача о минимальном разрезе ставятся не для
всех графов, а для конкретного вида орграфов, называемых сетями. Такой орграф может
служить моделью, например, компьютерной сети: узлами здесь будут компьютеры, один
из которых (обозначим его ) передаёт другому (обозначим его ) поток информации
посредством направленных каналов связи, которые являются дугами. Как нам известно,
любой канал связи имеет пропускную способность, которую мы можем указать для
каждого из них. Пример схемы такой компьютерной сети показан на рисунке 3.1.
Рисунок 3.1 – Схема компьютерной сети с
отмеченными пропускными способностями
Продолжая аналогии, можно представить сеть как сеть водопроводных труб, по
которым вода движется от истока к стоку. Или же как сеть электрических проводов, по
которым идёт ток.
Дадим формальное определение понятию «сеть».
Определение 3.1. Сеть – это связный взвешенный орграф , каждой
дуге
которого поставлено в соответствие неотрицательное число
–
пропускная способность дуги, а также выбраны две вершины: s – источник (исток) и t –
сток. Условимся также, что сеть не содержит петель, а между любыми двумя
вершинами может быть только одна дуга (прямая или обратная).
Пример сети представлен на рисунке 3.2.
8
Рисунок 3.2 - Сеть
3.2 Потоки
Поток в сети – это поток некоторого продукта (информации в компьютерной сети,
воды в водопроводе), который перемещается по сети от истока к стоку. Поток в сети
удовлетворяет двум простым, взятым “из жизни” правилам. Они формулируются ниже.
Формальное определение потока можно дать по аналогии с пропускными
способностями, через набор чисел
(весов), сопоставленных с дугами. Однако мы
дадим более формальное определение потока, используя понятие функции потока
(весовой функции). Заметим, что через функцию можно определить и пропускные
способности дуг: каждой дуге такая функция будет ставить в соответствие её пропускную
способность.
Определение 3.2. Поток ξ – это функция
, определённая на
множестве дуг сети, которая устанавливает соответствие между дугами сети и величинами
потока, проходящего через эти дуги. При этом функция ξ для
удовлетворяет
следующим соотношениям:
1) Уравнение сохранения потока
Для всех вершин
, кроме истока s и стока t, сумма потоков, входящих в
вершину, равна сумме потоков, исходящих из этой вершины:
где – некоторое число.
9
Формально это соотношение показывает, что за исключением источника и
стока поток в каждом узле сети не возникает и не исчезает. Весь поток,
попавший в узел сети, должен покинуть его.
2) Уравнение допустимости потока
Величина потока в дуге ограничена её пропускной способностью:
Отметим, что если дуги не существует, то величина её потока полагается равной
нулю.
Определение 3.3. Величина (значение) потока – это сумма потоков, выходящих
из истока, или сумма потоков, входящих в сток:
На рисунке 3.3 изображена сеть с заданным для неё потоком (величина потока
отделяется от следующей за ней пропускной способности символом “/”). Для этой сети
величина потока .
Рисунок 3.3 – Сеть с заданным потоком
Утверждение 3.1. Для произвольной сети множество потоков конечно и не пусто.
В частности, для всех дуг
является нулевым потоком.
Таким образом, для каждой сети найдётся хотя бы один поток, пусть и нулевой.
10
3.3 Задача о максимальном потоке в сети
Задача о максимальном потоке в сети заключается в том, чтобы для данной сети
построить такой поток ξ, чтобы его величина была максимальной.
Рассмотрим рисунок 3.4. На рисунке изображена сеть, для которой определён
некоторый поток величиной .
Рисунок 3.4 – Сеть с заданным потоком
Можно увидеть, что поток, заданный для изображённой на рисунке 3.4 сети, не
является максимальным: так, если перераспределить единицу потока с пути
на путь , и пустить по пути дополнительную единицу потока,
поток примет следующий вид (рисунок 3.5).
Рисунок 3.5 – Сеть с перераспределённым потоком
Перераспределённый поток приобрёл величину . Из рисунка можно увидеть,
что теперь поток является максимальным для этой сети: пропускные способности дуг
и , выходящих из истока, не позволяют задать поток большей величины.
11
Существуют также задачи на нахождение максимального потока с несколькими
истоками и (или) несколькими стоками. Такие задачи сводятся к обычной построением
эквивалентной сети с одним истоком и одним стоком. То есть, в сеть добавляется общий
исток s, из которого ведут рёбра бесконечной пропускной способности во все прежние
истоки. Аналогичным образом создаётся общий сток t. Пример представлен на рисунках
3.6 и 3.7.
Рисунок 3.6 – Задача с несколькими истоками и стоками
12
Рисунок 3.7 – Сведение задачи с несколькими стоками
и истоками к задаче с одним истоком и одним стоком
3.4 Разрезы
Введём понятие разреза.
Разделим множество вершин сети G на два непересекающихся
подмножества:
, где
.
Обозначим множество дуг сети , соединяющих вершины из
с вершинами
из
как
. Аналогично обозначим множество дуг, соединяющие вершины из
с вершинами из
как
.
Определение 3.4. Разрезом называется множество дуг
.
Пример разреза при разбиении множества на
и
приведён на рисунке 3.8. В данном случае разрез
.
13
Рисунок 3.8 – Пример разреза
Определение 3.5. Величиной (пропускной способностью)
разреза
называется сумма пропускных способностей дуг, входящих во множество
:
Так, для рисунка 3.8 величина разреза
.
Определение 3.6. Говорят, что разрез
отделяет исток от стока , если
.
Таким образом, мы можем сказать, что для сети на рисунке 3.8 разрез
отделяет s от t.
Теорема (Форд-Фалкерсон) 3.1. Величина максимального потока
из
s в t равна минимальной величине разреза, отделяющего s от t.
Для сети из рисунка 3.8 минимальный разрез
при
разбиении множества на
и
изображён на рисунке 3.9.
С неформальной точки зрения, минимальный разрез – это “узкие места” сети, то
есть те её дуги, которые не позволяют пустить по сети больший поток. Если нам
необходимо повысить максимальный поток через сеть, то минимальный разрез – это те
дуги, пропускную способность которых нам следует увеличивать в первую очередь.
14
Рисунок 3.9 – Минимальный разрез в сети
Видим, что пример на рисунке 3.9 иллюстрирует вывод теоремы Форда-
Фалкерсона.
4 Нахождение максимального потока и определение минимального разреза
Для поиска максимального потока и минимального разреза в сети существует
алгоритм Форда-Фалкерсона (Ford-Fulkerson algorithm). Этот алгоритм является одним из
первых алгоритмов решения данной задачи, но, несмотря на это, считается достаточно
эффективным. Для наглядности разобьём его на два алгоритма: алгоритм нахождения
максимального потока и алгоритм нахождения минимального разреза. Рассмотрим их.
4.1 Алгоритм нахождения максимального потока
Определение 4.1. Аугментальная цепь (дополняющая цепь, увеличивающая цепь)
– это цепь, соединяющая s и t, такая, что для каждой дуги
«прямого» направления
(ориентированной в направлении от s к t)
, а для каждой дуги
,
ориентированной в «обратном» направлении (от t к s),
.
Иными словами, если дуга цепи имеет «прямое» направление, нам важна
возможность повышения величины её потока. И наоборот, если дуга цепи имеет
«обратное» направление, нам важна возможность уменьшения величины её потока.
Ниже приводим описание алгоритма нахождения максимального потока.
Алгоритм нахождения максимального потока. Алгоритм начинает работу с
произвольного допустимого потока (например, нулевого), затем величина его
увеличивается с помощью систематического поиска всевозможных аугментальных цепей
от s к t. Для этого вершинам сети приписываются метки, указывающие, вдоль каких дуг и
на сколько может быть увеличен поток. Как только такая цепь находится, поток вдоль неё
увеличивается до максимального значения, все пометки в вершинах стираются, и вновь
полученный поток берётся в качестве исходного, и так до тех пор, пока такие потоки
можно построить.
Пусть
– текущая вершина,
– предыдущая вершина. Тогда вершине
приписывается пометка следующего вида:
или
, где
–
означает, что поток допускает увеличение вдоль дуги
;
– означает, что поток
допускает уменьшение вдоль дуги
.
– максимальная величина
дополнительного потока, который может проходить от s к
.
В первом приближении алгоритм может выглядеть следующим образом:
1. Задать сети произвольный допустимый поток (например, нулевой);
2. Найти аугментальную цепь, соединяющую s и t. Если такой нет, перейти к шагу 5;
16
3. Пустить через найденную цепь максимально возможный поток;
4. Перейти к шагу 2;
5. Конец.
Детализируем алгоритм:
1. Задать сети произвольный допустимый поток (например, нулевой);
2.
;
3. Пометить вершину
меткой ;
4. Выбрать одну из соседних вершин
вершины
, такую, что прямая дуга
допускает увеличение потока, или обратная дуга
допускает
уменьшение потока. Если таковых вершин нет, перейти к шагу 10;
5. Добавить
в строящуюся цепь. Пометить вершину
меткой:
Если поток допускает увеличение вдоль дуги
:
Пометить вершину
меткой
,
где
;
Иначе:
Если поток допускает уменьшение вдоль дуги
:
Пометить вершину
меткой
,
где
;
6.
;
7. Если
, перейти к шагу 4;
8. В полученной цепи для каждой дуги «прямого» направления увеличить поток на ,
для каждой дуги «обратного» направления уменьшить поток на ;
9. Очистить метки, перейти к шагу 2;
10. Конец: максимальный поток – текущий поток в сети.
Таким образом, когда алгоритм закончит работу, будет получен максимальный
поток. Отметим, что алгоритм заканчивает работу в случае, когда не найдётся вершин для
дальнейшего добавления к аугментальной цепи (шаг №5 подробного описания
алгоритма).
Заметим, что алгоритм не уточняет, как следует искать аугментальные цепи.
Перебирать все доступные аугментальные цепи от истока s к стоку t можно, к примеру, с
помощью поиска в глубину. В любом случае, алгоритм должен завершить свою работу
только тогда, когда аугментальных цепей от истока к стоку больше не существует.
4.2 Алгоритм нахождения минимального разреза
Алгоритм нахождения минимального разреза. Для того, чтобы определить
минимальный разрез, необходимо сначала найти максимальный поток в сети. Итак,
алгоритм будет выглядеть следующим образом.
1. Найти максимальный поток в сети;
17
2. Отметить все вершины, до которых можно добраться от истока s по «прямым» дугам,
допускающим повышение потока, или по «обратным» дугам, допускающим
уменьшение потока;
3. Конец: минимальный разрез – дуги, соединяющие помеченные вершины с
непомеченными.
То есть, после нахождения максимального потока нам необходимо посетить все
доступные вершины по «прямым» и «обратным» дугам, допускающим увеличение и
уменьшение потока соответственно. Таким образом мы найдём множество
, после чего
можно определить множество
и найти дуги, соединяющие вершины двух этих
множеств.
4.3 Особенности алгоритма Форда-Фалкерсона
Особенностью алгоритма является то, что он гарантированно сходится только для
целых пропускных способностей. В противном случае алгоритм может работать
бесконечно долго, не сходясь к оптимальному решению.
Поговорим о сложности алгоритма. На каждой итерации алгоритм пускает по
найденной аугментальной цепи поток в дополнение к уже имеющемуся в сети потоку.
Если пропускные способности всех рёбер — целые числа, значит, потоки через все дуги
также будут целыми числами. Следовательно, на каждой итерации алгоритм увеличивает
поток по крайней мере на единицу, а значит, он сойдётся не более чем за O(
) итераций,
где
— максимальный поток в графе. Каждая итерация выполняется не более чем за
O(m), где m — число рёбер в графе, тогда общее время работы алгоритма ограничено
O(
).
4.4 Пример применения алгоритма Форда-Фалкерсона
Теперь подробно рассмотрим применение алгоритма. Сеть, для которой будет
решаться задача, приведена на рисунке 4.1. Будем искать максимальный поток,
проходящий от вершины 1 к вершине 7 (то есть s = 1, t = 7).
18
Рисунок 4.1 - Задача
Рассмотрим все итерации алгоритма.
Первым делом задаём начальный поток. В качестве начального используем
нулевой поток (рисунок 4.2).
Рисунок 4.2 – Инициализация потока сети
После инициализации потока начинаем строить аугментальную цепь от вершины 1
к вершине 7. Начинаем с первой вершины, присваиваем ей метку . В данном
случае эта метка означает, что до вершины 1 поток может быть увеличен до сколь угодно
большого (однако величина потока, который пропустит сеть, всё же ограничена. Этот
максимально возможный поток мы и ищем). Шаг приведён на рисунке 4.3.
19
Рисунок 4.3 – Первый шаг первой итерации
Затем нам необходимо выбрать из «соседей» вершины 1 такого, к которому ведёт
дуга, допускающая увеличение потока (т.е. поток дуги не максимален), или же от
которого к вершине 1 ведёт дуга, допускающая уменьшение потока (т.е. поток дуги не
нулевой). Таких «соседей» два: вершины 2 и 4. Выберем, к примеру, вершину 4.
Переходим к рассмотрению вершины четыре: присваиваем ей метку и добавим в
цепь. В данном случае эта метка означает, что от вершины 1 до вершины 2 поток может
быть увеличен до 25 (несмотря на то, что вершина 1 может принять сколь угодно большой
поток, до вершины 4 по выбранному пути может пройти поток величиной не более, чем
25). Этот шаг приведён на рисунке 4.4.
Рисунок 4.4 – Второй шаг первой итерации
Аналогично выбираем следующую вершину из двух доступных: 5 и 6. Вершина 2
недоступна для добавления в цепь, т.к. её поток уже нулевой и не допускает уменьшения.
Выберем, к примеру, вершину 5. Пометим её соответствующей меткой и добавим в цепь.
20
Мы видим, что к вершине 5 может пройти только поток величиной не более, чем 18,
поэтому и метка будет содержать соответствующее значение (рисунок 4.5).
Рисунок 4.5 – Третий шаг первой итерации
Аналогично выбираем следующую вершину из двух доступных: 6 и 7. Выберем, к
примеру, вершину 7. Пометим её соответствующей меткой и добавим в цепь (рисунок
4.6).
Рисунок 4.6 – Четвёртый шаг первой итерации
Мы подошли к концу первой итерации. Мы выяснили, что найденная цепь может
провести дополнительный поток, не превышающий значения 18. Так как все дуги в цепи
«прямого» направления, увеличиваем поток каждой из них на 18. Получили новый поток,
который берём за исходный (рисунок 4.7).
21
Рисунок 4.7 – Поток, полученный после первой итерации
Вновь начинаем искать аугментальную цепь, но уже с новым потоком в сети. На
рисунках 4.8, 4.9, 4.10, 4.11, 4.12 представлены шаги второй итерации.
Рисунок 4.8 – Первый шаг второй итерации
Рисунок 4.9 – Второй шаг второй итерации
22
Обратим внимание, что на третьем шаге вершине 3 будет присвоена метка
, потому что несмотря на большую пропускную способность дуги (2,3) к вершине
2 может быть дополнительно подведено только 15 единиц потока.
Рисунок 4.10 – Третий шаг второй итерации
Рисунок 4.11 – Четвёртый шаг второй итерации
23
Рисунок 4.12 – Пятый шаг второй итерации
Мы подошли к концу второй итерации. Как видим, найденная цепь может провести
дополнительный поток, не превышающий значения 4. Так как все дуги в цепи «прямого»
направления, увеличиваем поток каждой из них на 4. Получили новый поток, который
берём за исходный (рисунок 4.13).
Рисунок 4.13 – Поток, полученный после второй итерации
Вновь начинаем искать аугментальную цепь, но уже с новым потоком в сети. На
рисунках 4.14, 4.15, 4.16, 4.17, 4.18 представлены шаги третьей итерации.
24
Рисунок 4.14 – Первый шаг третьей итерации
Рисунок 4.15 – Второй шаг третьей итерации
Рисунок 4.16 – Третий шаг третьей итерации
25
Рисунок 4.17 – Четвёртый шаг третьей итерации
Рисунок 4.18 – Пятый шаг третьей итерации
Мы подошли к концу третьей итерации. Как видим, найденная цепь может
провести дополнительный поток, не превышающий значения 3. Так как все дуги в цепи
«прямого» направления, увеличиваем поток каждой из них на 3. Получили новый поток,
который берём за исходный (рисунок 4.19).
26
Рисунок 4.19 – Поток, полученный после третьей итерации
Вновь начинаем искать аугментальную цепь, но уже с новым потоком в сети. На
рисунках 4.20, 4.21, 4.22, 4.23 представлены шаги четвёртой итерации.
Рисунок 4.20 – Первый шаг четвёртой итерации
Рисунок 4.21 – Второй шаг четвёртой итерации
27
Рисунок 4.22 – Третий шаг четвёртой итерации
Рисунок 4.23 – Четвёртый шаг четвёртой итерации
Мы подошли к концу четвёртой итерации. Как видим, найденная цепь может
провести дополнительный поток, не превышающий значения 6. Так как все дуги в цепи
«прямого» направления, увеличиваем поток каждой из них на 3. Получили новый поток,
который берём за исходный (рисунок 4.24).
28
Рисунок 4.24 – Поток после четвёртой итерации
Вновь начинаем искать аугментальную цепь, но уже с новым потоком в сети. На
рисунках 4.25, 4.26, 4.27, 4.28, 4.29 представлены шаги пятой итерации.
Рисунок 4.25 – Первый шаг пятой итерации
Рисунок 4.26 – Второй шаг пятой итерации
29
Рисунок 4.27 – Третий шаг пятой итерации
На третьем шаге для добавления в строящуюся цепь доступна только вершина 6:
вершины 3 и 6 соединяет дуга «обратного» направления, и при этом её поток может быть
уменьшен на 3 единицы.
Рисунок 4.28 – Четвёртый шаг пятой итерации
30
Рисунок 4.29 – Пятый шаг пятой итерации
Как видим, доступных для перехода вершин нет. Значит, работа алгоритма
закончена: максимальный поток равен текущему потоку,
. Отмечаем вершины,
доступные из истока по «прямым» и «обратным» дугам, допускающим увеличение и
уменьшение потока соответственно. Получили, что минимальный разрез проходит по
дугам, соединяющим отмеченные вершины с неотмеченными: (4;5), (5;6), (3;5), (3;7).
Результат представлен на рисунке 4.30 (красным выделены дуги, входящие в
минимальный разрез).
Рисунок 4.30 – Результат работы алгоритма
Заметим, что если бы эта цепь была завершена (т.е. соединила бы вершину 1 с
вершиной 7), то поток был бы увеличен по дугам «прямого» направления на полученную
величину, а по дугам «обратного» направления (таким, как дуга между вершинами 3 и 6),
наоборот, уменьшен на эту же величину.
31
Заметим также и то, что в зависимости от выбираемых на каждой итерации
маршрутов решения могут быть разными. Величина максимального потока и
минимальный разрез для одной и той же сети, без сомнений, всегда будут одинаковыми,
однако распределение потока по дугам может отличаться. Пример представлен на рисунке
4.31.
Рисунок 4.31 – Пример различного распределения потока
4.5 Максимальность потока, найденного алгоритмом Форда-Фалкерсона
Алгоритм работает, и действительно находит максимальный поток – это кажется
практически очевидным. А есть ли формальный “маркер” правильности нахождения
максимально потока?
Теорема (достаточное условие максимальности потока) 4.1. Поток на
заданной сети с истоком s и стоком t является максимальным тогда и только тогда,
когда существует разрез
, отделяющий s от t, такой, что величина потока
совпадает с пропускной способностью этого разреза:
.
Теорема 4.1 отсылает к теореме Форда-Фалкерсона (теорема 3.1), которая говорит о
совпадении величины максимального потока с пропускной способностью минимального
32
разреза. Однако каким образом это достигается? Обратим внимание на следующую
формулу:
Формула показывает, что поток, достигающий стока t – это поток, попадающий в
вершины множества
, и не возвращающийся в вершины множества
. Однако, для
максимального потока
этот поток имеет величину, равную пропускной способности
разреза – суммарной пропускной способности его “прямых” дуг. Из этого следует, что
“обратные” дуги минимального разреза – пустые. Это иллюстрируется и примером
(рисунок 4.30).
5 Связанные задачи
Итак, нами была рассмотрена задача нахождения максимального потока и один из
алгоритмов её решения. Скажем несколько слов о связанных с ней задачах, для решения
которых используется поиск максимального потока.
5.1 Задача о максимальном потоке минимальной стоимости
Как можно понять из названия, задача о максимальном потоке минимальной
стоимости является дальнейшим усложнением рассмотренной нами задачи о
максимальном потоке. Постановка задачи звучит следующим образом.
Дана сеть , каждой её дуге
, помимо пропускной способности
,
назначена стоимость перемещения по ней единицы потока
. Необходимо найти поток
максимальной величины, суммарная стоимость которого, складывающаяся из
перемещения единиц потока по всем его дугам, минимальна.
Алгоритм решения задачи о максимальном потоке минимальной стоимости
использует алгоритм Форда-Фалкерсона на начальном этапе, для запуска по сети
максимального потока. После этого строится так называемая остаточная сеть , которая
содержит те же вершины, что и сеть , и одна или две дуги на каждую дугу
сети ,
которые определяются следующим образом. Если
, то в остаточную сеть
включается ребро
с пропускной способностью
и стоимостью перемещения
, и если
, то в остаточную сеть включается ребро
с пропускной
способностью
и стоимостью перемещения
. Пример сети и построенной
для неё остаточной сети приведён на рисунке 5.1 (5.1а и 5.1б соответственно), в скобках
указаны стоимости перемещения. Таким образом, стоимость изображённого на рисунке
5.1а потока равна 43 единицы.
а)
б)
Рисунок 5.1 – Пример сети и её остаточной сети
34
Дальнейшие шаги алгоритма определяются содержанием следующей леммы.
Лемма 5.1. Максимальный поток сети является максимальным потоком
минимальной стоимости тогда и только тогда, когда остаточная сеть не содержит
(ориентированный) цикл с отрицательной стоимостью.
Таким образом, происходит поиск циклов отрицательной стоимости в остаточной
сети, и увеличение в них потока на максимально возможную величину. Алгоритм
завершает работу тогда, когда цикла отрицательной стоимости в остаточной сети не
нашлось.
Так, для сети, изображённой на рисунке 5.1а, остаточная сеть (рисунок 5.1б)
содержит цикл отрицательной стоимости (его стоимость равна -1).
Наибольший поток, который может быть пущен в этом цикле, равен единице. Изменим
поток в исходной сети, добавляя единицу к потоку дуг, соответствующих дугам с
положительной стоимостью в найденном цикле в остаточной сети (прямые дуги) и
вычитая единицу из потока дуг, соответствующих дугам с отрицательной стоимостью в
найденном цикле в остаточной сети (обратные дуги). Такая модификация не изменит
величину потока в сети, однако уменьшится его стоимость. Если
– величина
дополнительного потока, который может быть пущен по найденному циклу, а
–
стоимость этого цикла (отрицательное число), то от перераспределения потоков
стоимость потока в сети уменьшится на величину
. Результат
перераспределения потока для сети, изображённой на рисунке 5.1, и её остаточная сеть
изображены на рисунке 5.2 (5.2а и 5.2б соответственно). Стоимость потока при этом
снизилась на единицу и составила 42. Мы видим, что отрицательного цикла в остаточной
сети больше нет, значит, данный максимальный поток имеет минимальную стоимость.
а)
б)
Рисунок 5.2 – Максимальный поток минимальной стоимости
35
Рассмотренный метод поиска максимального потока минимальной стоимости в
сети называется алгоритмом вычёркивания циклов (cycle-canceling algorithm), или
алгоритмом устранения отрицательных циклов в остаточной сети.
5.2 Задача о наибольшем паросочетании в двудольном графе
Определение 5.1. Паросочетание (независимое множество рёбер) – это множество
рёбер, в котором никакие два ребра не смежны.
Определение 5.2. Паросочетание называется максимальным, если к нему
невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам
паросочетания. Пример максимального паросочетания приведён на рисунке 5.3.
Рисунок 5.3 – Максимальное паросочетание
Определение 5.3. Паросочетание называется наибольшим, если оно содержит
максимальное количество рёбер. Пример наибольшего паросочения приведён на рисунке
5.4.
Рисунок 5.4 – Наибольшее паросочетание
36
Наибольшее паросочетание всегда является максимальным, однако не каждое
максимальное паросочетание является наибольшим. Это замечание наглядно
демонстрируется приведёнными выше примерами.
Определение 5.4. Двудольным графом называется такой граф, множество
вершин которого разбивается на два непересекающихся подмножества
и
, при этом
смежными могут быть только вершины, принадлежащие разным подмножествам – любые
две вершины каждого подмножества несмежны. Обычно такой граф обозначают как
. Пример двудольного графа изображён на рисунках 5.3 и 5.4 (
,
).
Для нахождения наибольшего паросочетания можно использовать алгоритм поиска
максимального потока. Для этого необходимо добавить две дополнительные вершины:
вершину-исток s и вершину-сток t. Исток s соединим со всеми вершинами множества
,
сток t соединим со всеми вершинами множества
. Всем рёбрам получившегося графа
присвоим единичную пропускную способность, и ориентируем их в направлении от
истока к стоку. Для изображённого выше графа модификация выглядит следующим
образом (рисунок 5.5). Пропускные способности всех дуг равны единицы, и не показаны
на рисунке.
Рисунок 5.5 – Модификация графа для нахождения наибольшего паросочетания
37
Само собой, величину максимального потока в такой сети можно легко посчитать и
устно. Однако, рёбра, по которым пройдёт этот поток, и будут составлять наибольшее
паросочетание графа (в расчёт не берутся добавленные дуги, связанные с истоком s и
стоком t).
Похожим образом можно решать задачу о совершенных паросочетаниях.
5.3 Задача о совершенных паросочетаниях
Определение 5.5. Пусть
– двудольный граф. Совершенным
паросочетанием из
в
является паросочетание, покрывающее вершины
(т.е.
включающее все вершины из него).
Совершенное паросочетание всегда является максимальным.
Задача о совершенных паросочетаниях может быть сформулирована как задача о
свадьбах. Её постановка будет звучать следующим образом.
Пусть имеется конечное множество юношей, каждый из которых знаком с
некоторым подмножеством конечного множества девушек. В каком случае всех юношей
можно женить так, чтобы каждый женился на знакомой девушке?
В данном случае множество юношей и множество девушек – это соответственно
подмножества
и
двудольного графа
. Совершенным паросочетанием из
в
мы решим задачу о свадьбах, то есть подберём невесту каждому юноше. Если же нам
понадобится выдать замуж всех невест, то необходимо будет найти совершенное
паросочетание из
в
. Для решения этой задачи также может быть использован
алгоритм нахождения максимального потока, однако для этого его необходимо
модифицировать. Направление паросочетания (из
в
или из
в
) можно задать с
помощью изменения направления потока.
Совершенное паросочетание существует не всегда. Достаточное условие
существования решения задачи о совершенном паросочетании формулирует теорема
Холла, которая носит название «Теорема о свадьбах».
Теорема (Холл) 5.1. Пусть
– двудольный граф. Совершенное
паросочетание из
в
существует тогда и только тогда, когда для любого натурального
k любые k вершин доли
связаны по крайней мере с k вершинами доли
.
38
Кроме этого, алгоритм поиска максимального потока может быть применён для
решения задачи о назначениях, заключающейся в оптимальном назначении работников на
доступные должности. Эта задача также является задачей о паросочетаниях.
6 Паросочетания
Пусть задан неориентированный граф .
Определение 6.1. Паросочетанием (англ. matching) в графе G называется
подмножество рёбер
, такое, что любой вершине графа инцидентно не более
одного ребра из M.
Иными словами, паросочетание M – это набор попарно несмежных рёбер графа,
набор рёбер, которые не имеют общих вершин.
На рисунке 6.1 приведён пример паросочетания. Рёбра, входящие в паросочетание,
выделены цветом.
Рисунок 6.1 – Пример паросочетания
Ребро {u,v}, входящее в некоторое паросочетание графа, называют
паросочетаюшим. При этом вершины u и v, которые оно соединяет, называются
паросочетанными. Иногда паросочетанные вершины также называют покрытыми (англ.
matched), или же насыщенными (англ. saturated) паросочетанием. Так, для графа,
изображённого на рисунке 6.1, паросочетанные вершины 1 и 3 имеют паросочетающее
ребро {1,3}, паросочетанные вершины 2 и 6 – паросочетающее ребро {2,6},
паросочетанные вершины 4 и 5 – паросочетающее ребро {4, 5}.
Определение 6.2. Мощностью паросочетания (англ. matching cardinality)
называется количество рёбер в нём.
В одном графе может существовать несколько паросочетаний, образованных
разными паросочетающими рёбрами. Эти паросочетания могут различаться по своим
свойствам, в т.ч. по мощности и по количеству покрываемых вершин графа.
40
Определение 6.3. Максимальное паросочетание (максимальное по мощности, англ.
maximum cardinality matching, maximum matching) – это паросочетание, мощность
которого максимальна среди всех возможных паросочетаний в данном графе.
Определение 6.4. Наибольшее паросочетание (максимальное по включению, англ.
maximal matching) – это паросочетание, которое не содержится ни в каком другом
паросочетании данного графа, т.е. к нему нельзя добавить ни одно другое ребро графа, и
при этом получить большее по мощности паросочетание.
Определение 6.5. Совершенное паросочетание (полное паросочетание, англ.
perfect matching) – это паросочетание, покрывающее все вершины графа.
Отметим, что среди некоторых авторов существуют разночтения при определении
максимального и наибольшего паросочетания: в некоторых источниках под наибольшим
паросочетанием понимается максимальное, а под максимальным, наоборот, наибольшее.
Скорее всего это идёт от неоднозначного перевода английских слов «maximum» и
«maximal». Однако, в дальнейшем мы будем придерживаться данных выше определений.
Рассмотрим примеры. Так, паросочетание, представленное на рисунке 6.1, является
максимальным для данного графа. Кроме того, оно же является и наибольшим, и
совершенным. На рисунке 6.2 представлен пример наибольшего паросочетания, которое,
однако, не является ни максимальным (на рисунке 6.1 мы уже видели паросочетание
большей мощности для данного графа), ни совершенным (вершины 5 и 6 не покрыты им).
Рисунок 6.2 – Пример наибольшего сочетания
Утверждение 6.1. Максимальное паросочетание является также наибольшим.
Утверждение 6.2. Совершенное паросочетание является также наибольшим и
максимальным.
Соответственно, в теории графов существует три самостоятельные задачи: задача о
максимальном паросочетании, задача о наибольшем паросочетании, и задача о
41
совершенном паросочетании, которые заключаются в поиске соответствующего
паросочетания в исходном графе.
Наибольшее паросочетание может быть найдено простым «жадным» алгоритмом
вида «пока это возможно, берём в паросочетание новое ребро». Отметим, что задача о
наибольшем паросочетании может формулироваться по-разному: может потребоваться
найти любое наибольшее паросочетание, или же наибольшее паросочетание наименьшей
мощности. В этом случае будут различаться и подходы к решению.
Две другие задачи являются более содержательными, и, соответственно, требуют
более содержательного подхода к решению. Мы так или иначе рассмотрим обе эти задачи.
7 Задача о максимальном паросочетании
7. 1 Общая постановка задачи
Дан неориентированный граф . Требуется найти паросочетание
максимальной мощности (максимальное паросочетание), т.е. решить задачу:
.
Это постановка задачи в общем виде, для произвольного графа. Однако, на
практике данная задача может быть рассмотрена отдельно для двудольных графов – для
них существуют более простые алгоритмы решения. С них и начнём.
7.2 Постановка задачи для двудольных графов
Напомним определение двудольного графа.
Определение 7.1. Двудольным графом (англ. bipartite graph)
называется граф , множество вершин V которого разбивается на два непустых
непересекающихся подмножества
, так что каждое ребро имеет вид {v
1
, v
2
}, где
v
1
V
1
, v
2
V
2
. Таким образом, каждое ребро соединяет вершину из V
1
с вершиной из V
2
, и
не существует ребра, соединяющего две вершины одного и того же множества (V
1
или V
2
).
Пример двудольного графа изображён на рисунке 7.1. В данном случае множество
вершин графа V разбивается на подмножества
и
.
Рисунок 7.1 – Пример двудольного графа
Постановка задачи о максимальном паросочетании для двудольного графа в целом
не меняется. Для её решения можно использовать несколько алгоритмов, в том числе
свести задачу к задаче поиска максимального потока в сети.
7.3 Сведение задачи к задаче о максимальном потоке в сети
43
Мы уже упоминали о связи между задачей о максимальном паросочетании и
задачей о максимальном потоке в сети. Здесь мы расскажем об этом подробнее.
Один из способов найти максимальное паросочетание в двудольном графе – свести
задачу к поиску максимального потока в сети.
Продемонстрируем это на примере графа, изображённого на рисунке 7.1. Для того,
чтобы применить алгоритм поиска максимального потока, его необходимо превратить в
сеть. Для этого нужно добавить две дополнительные вершины: вершину-исток s и
вершину-сток t. Исток s соединим со всеми вершинами множества
, сток t соединим со
всеми вершинами множества
. Всем рёбрам получившегося графа присвоим единичную
пропускную способность, и ориентируем их в направлении от истока к стоку.
Получившаяся модификация исходного графа представлена на рисунке 7.2 (исток –
вершина 0, сток – вершина 9). Пропускные способности всех дуг равны единицы, и не
показаны на рисунке. Такую сеть, полученную из двудольного графа, иногда называют
сетью паросочетаний (англ. network flow).
После преобразования двудольного графа в сеть паросочетаний достаточно
применить к ней алгоритм поиска максимального потока из истока s в сток t. Например,
можно применить классический алгоритм Форда-Фалкерсона (англ. Ford-Fulkerson
algorithm), или алгоритм Диница (англ. Dinic’s algorithm).
Рисунок 7.2 – Сеть паросочетаний исходного графа
44
Само собой, величину найденного максимального потока в такой сети посчитать
легко. Однако, рёбра, по которым пройдёт этот поток, и будут составлять максимальное
паросочетание графа G (в расчёт, естественно, не берутся добавленные дуги, связанные с
истоком s и стоком t).
Если использовать для поиска максимального потока алгоритм Форда-Фалкерсона,
решение найдётся за время порядка , где n – количество вершин в графе, m –
количество рёбер в нём.
7.4 Алгоритм Куна решения задачи на двудольных графах
Помимо описанного выше алгоритма решения задачи путём её сведения к задаче о
максимальном потоке, существует ещё несколько алгоритмов поиска максимального
паросочетания в двудольном графе. Среди них – алгоритм Куна (англ. Kuhn's Algorithm for
Maximum Bipartite Matching) и алгоритм Хопкрофта-Карпа-Карзанова (англ. Hopcroft-
Karp-Karzanov algorithm), которые похожи друг на друга. Мы рассмотрим алгоритм Куна
как классический алгоритм решения данной задачи.
Перед тем, как дать нужные определения, заметим, что под словом «путь» мы
будем понимать некоторый простой путь – путь, проходящий по любой вершине или
ребру графа не более одного раза.
Определение 7.2. Чередующийся путь (чередующаяся цепь, англ. alternating path)
относительно паросочетания M – это путь, в котором рёбра поочерёдно то принадлежат
паросочетанию M, то не принадлежат ему.
Чередующиеся пути могут быть трёх типов:
1) чередующийся путь между двумя покрытыми вершинами – рисунок 7.3.
Рисунок 7.3 – Первый тип чередующегося пути
2) чередующийся путь между двумя непокрытыми (свободными) вершинами – рисунок
7.4.
Рисунок 7.4 – Второй тип чередующегося пути
45
3) чередующийся путь между покрытой и непокрытой вершинами – рисунок 7.5.
Рисунок 7.5 – Третий тип чередующегося пути
На рисунках выше зелёным цветом выделены дуги, принадлежащие некоторому
паросочетанию M. В первом случае вершины 1 и 6 (первая и последняя) покрыты
паросочетанием, т.к. инциденты дугам, входящим в него. Во втором случае всё с
точностью наоборот – вершины 1 и 8 не покрыты паросочетанием. В третьем случае
покрыта вершина 5, но не покрыта вершина 1.
Определение 7.3. Аугментальный путь (пополняющий путь, увеличивающий путь,
англ. augmenting path) относительно паросочетания M – это чередующийся путь между
двумя непокрытыми вершинами.
Иными словами, аугментальный путь начинается и кончается непокрытыми
(иногда их называют свободными, англ. free) вершинами. Это случай чередующегося
маршрута, изображённый на рисунке 7.4.
Рассмотрим пример аугментального пути в графе, изображённом на рисунке 7.1.
Пусть в графе зафиксировано паросочетание из рёбер {2, 3}, {4, 5}, {6, 7}. Проведём через
данное паросочетание аугментальный путь 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8. В аугментальном
пути зелёным цветом выделены рёбра паросочетания, красным – рёбра, не входящие в
него (рисунок 7.6). Для удобства рёбрам были добавлены стрелочки по направлению хода
по пути.
Рисунок 7.6 – Пример аугментального пути
46
Последовательный поиск аугментальных путей позволяет постепенно найти
максимальное паросочетание в двудольном графе. Для этого проводят так называемое
чередование.
Определение 7.4. Чередование (вдоль аугментального пути P) – это удаление из
текущего найденного паросочетания всех рёбер, входящих в аугментальный путь P, и
добавление в него оставшихся рёбер этого аугментального пути P.
Для примера с рисунка 7.6 в результате чередования из паросочетания будут
удалены рёбра {2, 3}, {4, 5}, {6, 7} – они входят в построенный аугментальный путь и
принадлежат паросочетанию. Затем в паросочетание будут добавлены рёбра {1, 2}, {3, 4},
{5, 6}, {7, 8}.
Аугментальный путь всегда состоит из нечётного количества рёбер, при этом
первое и последнее ребро не входит в паросочетание. Среди оставшихся рёбер не входит в
паросочетание k вершин, а входит – (k + 1). В результате, после чередования из
паросочетания будет удалено (k + 1) ребро, а добавлено в него будет (k + 2) рёбер. То
есть, при каждом чередовании мощность текущего найденного паросочетания будет
увеличиваться на единицу. Благодаря этому увеличивающие пути и получили своё
название.
Теорема (Клод Берж, англ. Claude Berge, 1957 г.) 7.1 Паросочетание M в графе
G = (V, E) является наибольшим тогда и только тогда, когда для него не существует
аугментального пути.
Алгоритм Куна – это прямое применение теоремы Бержа. Алгоритм начинает
работу с пустого паросочетания, и затем последовательно ищет аугментальные пути и
увеличивает мощность текущего паросочетания. Заканчивает работу алгоритм тогда,
когда аугментальных цепей для текущего паросочетания больше не существует.
Алгоритм (алгоритм Куна)
Пусть граф G = (V, E) из n вершин дан в виде матрицы смежности g. Текущее
паросочетание matching – пустое. Алгоритм Куна будет заключаться в последовательном
поиске аугментальных путей из всех вершин графа. В результате паросочетание matching
окажется максимальным.
Для поиска аугментальных путей можно воспользоваться поиском в ширину или
поиском в глубину. При описании псевдокода будет использоваться поиск в глубину.
47
Ниже приводим псевдокод алгоритма Куна с комментариями.
// Обход в глубину, реализующий поиск аугментальной цепи из вершины vertex.
// Возвращает true, если путь найден, false - иначе.
// По ссылке изменяет массив matching.
bool DFS(int vertex, bool used[], int[] matching, int g[][], int n) {
if (used[vertex])
return false;
used[vertex] = true;
// Ищем среди смежных вершин ту, в которую можем перейти,
// и запускаем поиск аугментальной цепи из неё.
// Если вершина свободна, то можно сразу идти в неё.
// Если она покрыта, то в неё можно идти только тогда, из её пары
// можно найти какую-то другую вершину.
for nextVertex in g[vertex] {
if (matching[nextVertex] == -1 or DFS(matching[nextVertex], used, matching, g, n)) {
matching[nextVertex] = vertex;
return true;
}
}
return false
}
// Основная функция алгоритма.
// Принимает на вход матрицу графа g и количество вершин n.
// Возвращает целочисленный массив с индексами от 1 до n,
// в котором по номеру вершины содержится номер её пары
// (или -1, если вершина не покрыта паросочетанием)
int[] KuhnAlgorithm(int g[][], int n) {
int matching[1..n]; // массив, по номеру вершины хранящий её пару
// (или '-1', если она не покрыта паросочетанием)
fill(matching, -1); // заполнить массив matching значениями '-1'
bool used[1..n]; // булев массив, содержащий признаки посещения вершин
// Из каждой вершины запускаем поиск аугментальной цепи,
// предварительно очистив признаки посещения вершин
for vertex := 1 to n do {
fill(used, false); // заполнить массив used значениями 'false'
DFS(vertex, used, matching, g, n);
}
return matching;
}
Алгоритм Куна отработает за время порядка , где n – количество вершин в
графе, m – количество рёбер в нём, что в худшем случае есть
. Если же перед
48
запуском алгоритма для исходного графа будет известно разбиение на две доли V
1
и V
2
, то
можно запускать поиск аугментальных путей не из каждой из n вершин, а только из
вершин первой доли. Такая оптимизация даст нам сложность порядка
, что в
худшем случае есть
.
7.5 Алгоритм Эдмондса решения задачи на произвольных графах
Алгоритм Эдмондса поиска максимального паросочетания, или алгоритм сжатия
цветков (алгоритм стягивания цветков, алгоритм вырезания соцветий, англ. Blossom
algorithm) – это также алгоритм построения максимального паросочетания в графах,
который, однако, найдёт решение в произвольном графе.
Алгоритм Эдмондса заимствует некоторые определения из уже рассмотренного
алгоритма Куна. Под чередующимся маршрутом, аугментальной цепью и чередованием
вдоль аугментальной цепи мы будем понимать ровно то же, что понимали до этого. Более
того, алгоритм сжатия цветков работает на примерно тех же принципах, что и алгоритм
Куна. Его базой также является теорема Берджа, и он также подразумевает
последовательный поиск аугментальных цепей и чередование вдоль них до тех пор, пока
это возможно. Если это так, то почему для поиска максимального паросочетания в
произвольном графе не подходит сам алгоритм Куна?
Рассмотрим пример. На рисунке 7.7 представлен граф, в нём зафиксировано
паросочетание из одного ребра {2, 3}.
Рисунок 7.7 – Пример графа с нечётным циклом
Для данного паросочетания существует аугментальная цепь 1 – 3 – 2 – 4. Однако,
алгоритм Куна рискует не найти его. Так, если запустить поиск аугментальной цепи из
вершины 1, и если поиск пойдёт сначала в вершину 2, то он зайдёт в тупик – в вершину 3,
и аугментальная цепь не будет найдена. С другой стороны, если поиск пойдёт сначала в
вершину 3, то аугментальный путь будет найден. Также в данном случае исправит
ситуацию запуск обхода из вершины 4. Иными словами, в такой ситуации будет важен
49
порядок обхода. И может сложиться так, что алгоритм Куна пойдёт в неправильном
направлении и в конце концов зайдёт в тупик, так и не найдя максимальное
паросочетание.
Такая ситуация может сложиться тогда, когда в графе есть насыщенные циклы
нечётной длины (пример такого цикла и приведён на рисунке 7.7).
Определение 7.5. Насыщенный цикл нечётной длины (насыщенный нечётный
цикл) – это цикл нечётной длины, длина которого составляет (2k + 1) ребро, и из них
ровно k рёбер насыщены некоторым паросочетанием.
В двудольных графах насыщенных нечётных циклов мы не встретим, а в случае
произвольного графа их наличие может «сломать» весь алгоритм. Основной задачей,
которую нам предстоит решить, является поиск аугментальной цепи с учётом
возможности наличия таких циклов.
Насыщенный цикл нечётной длины всегда имеет ровно одну вершину, не
покрытую рёбрами паросочетания – назовём её базой (корнем, англ. base, root). Пусть к
базовой вершине примыкает чередующийся путь чётной (возможно, нулевой) длины,
начинающийся в непокрытой паросочетанием вершине – такой путь назовём стеблем
(англ. stem). Сам подграф, образованный насыщенным нечётным циклом, назовём
цветком (соцветием, англ. blossom).
Рассмотрим пример, изображённый на рисунке 7.8. Здесь стебель – это путь от
вершины s
1
к вершине b (он обведён зелёным овалом). Базовая вершина – это вершина b.
Цветок образован вершинами b, b
1
, b
2
, b
3
, b
4
, b
5
, b
6
(он обведён красным кругом). Рёбра,
принадлежащие некоторому зафиксированному паросочетанию, выделены оранжевым
цветом.
50
Рисунок 7.8 – Цветок, база и стебель в графе
Для того, чтобы избежать тупиковых ситуаций, связанных с нечётными циклами,
алгоритм Эдмондса предлагает сжимать такие цветки.
Определение 7.6. Сжатие цветка (стягивание цветка, англ. blossom shrinking) –
это сжатие всего нечётного цикла в одну псевдо-вершину (супер-вершину). При этом все
рёбра, инцидентные вершинам этого цикла, становятся инцидентными супер-вершине.
Сжатие цветка происходит путём стягивания всех рёбер данного цветка.
Таким образом, алгоритм Эдмондса предусматривает поиск и сжатие всех цветков.
В результате из исходного графа G будет получен граф G’, который называется сжатым
(англ. contracted) или поверхностным (англ. surface). В полученном графе G’ уже можно
искать аугментальные цепи простым обходом в глубину или в ширину. После нахождения
аугментальной цепи в сжатом графе необходимо «развернуть» цветки обратно,
восстановив тем самым полную аугментальную цепь в исходном графе.
На рисунке 7.9 изображён сжатый цветок для графа, представленного на рисунке
7.8.
51
Рисунок 7.9 – Сжатый цветок
Сжатие цветков, как может показаться на первый взгляд, не нарушает структуру
исходного графа G. Это значит, что все аугментальные цепи, существующие в графе G,
будут существовать и в графе G’. Об этом говорит соответствующая теорема.
Теорема (Джек Эдмондс, англ. Jack Edmonds, 1965 г.) 7.2. В графе G’ существует
аугментальный путь тогда и только тогда, когда существует аугментальный путь в G.
Теперь приведём формальное описание алгоритма на языке псевдокода.
Алгоритм (алгоритм сжатия цветков)
В первом приближении алгоритм можно представить следующим образом.
// Обход в ширину, реализующий поиск аугментальной цепи из свободной вершины
root.
// Возвращает последнюю посещённую вершину, если путь найден, -1 - иначе.
int FindAugmentPath(int root, int g[][], int n, int[] matching) {
Обход в ширину:
int v = текущаяВершина;
Для каждого ребра из v:
Если обнаружен цикл нечётной длины, сжать его;
Если достигнута свободная вершина v, return v;
Если достигнута несвободная вершина, то добавить в очередь смежную ей в
паросочетании;
return -1;
}
// Основная функция алгоритма.
// Принимает на вход матрицу графа g и количество вершин n.
// Возвращает целочисленный массив с индексами от 1 до n,
// в котором по номеру вершины содержится номер её пары
// (или -1, если вершина не покрыта паросочетанием)
52
void EdmondsAlgorithm(int g[][], int n) {
int matching[1..n]; // массив, по номеру вершины хранящий её пару
// (или '-1', если она не покрыта паросочетанием)
fill(matching, -1); // заполнить массив matching значениями '-1'
for vertex := 1 to n do
if (вершина vertex не в паросочетании) {
int lastVertex = FindAugmentPath (vertex, g, n, matching);
if (lastVertex != -1)
выполнить чередование вдоль пути из vertex в lastVertex;
}
}
Как было сказано выше, в двудольных графах нет циклов нечётной длины. Это
значит, что сжатие цветков там не требуется. Если убрать сжатие цветков, то получим уже
знакомый алгоритм – алгоритм Куна.
8 Задача о совершенном паросочетании
8.1 Общая постановка задачи
Напомним, что совершенное паросочетание (полное паросочетание, англ. perfect
matching) – это паросочетание, покрывающее все вершины графа. Теперь поставим задачу
о совершенном паросочетании для произвольного графа.
Пусть дан неориентированный граф . Необходимо найти паросочетание
M, покрывающее все вершины графа, то есть найти
.
Ранее нами уже было дано утверждение (утверждение 6.2), в соответствии с
которым совершенное паросочетание является также наибольшим и максимальным.
Приведём ещё одно утверждение.
Утверждение 8.1. Если в графе G существует совершенное паросочетание, то
найденное максимальное паросочетание M является совершенным.
В соответствии с этим утверждением искать совершенное паросочетание следует
по тем же алгоритмам, которые используются для поиска максимального паросочетания.
Однако, необходим критерий, который бы мог позволить определить существование
совершенного паросочетания в исходном графе.
Определение 8.1. Дан граф G = (V, E). Две вершины u, v
V называются
связанными в графе G, если в нём существует путь из u в v. Считается, что вершина
связана сама с собой.
Определение 8.2. Граф G = (V, E) называется связным, если в нём любые две
вершины u, v
V являются связанными, т.е. между любой парой вершин существует путь.
Определение 8.3. Компонента связности графа G = (V, E) – это максимальный
связный подграф в графе. Иными словами, это такое подмножество S
V вершин графа G,
что для любых двух вершин u, v
S существует путь из одной в другую, и не существует
пути из любой вершины u
S в любую вершину t
V \ S, не входящую в подмножество S.
На рисунке 8.1 приведён пример графа с двумя компонентами связности. Одна
компонента связности образована вершинами 1, 2 и 3, вторая – вершинами 4 и 5.
54
Рисунок 8.1 – Граф из двух компонент связности
Приведём необходимое условие существования совершенного паросочетания в
произвольном графе. Подчеркнём, что оно не является достаточным.
Утверждение 8.2. Если в графе существует совершенное паросочетание, то в
каждой его компоненте связности чётное число вершин.
Почему это так? Дело в том, что в любом графе, состоящем из нечётного
количества вершин, не может быть совершенного паросочетания. Приведём теперь
достаточное условие существования совершенного паросочетания в произвольном графе.
Таким условием является теорема Татта (англ. Tutte theorem).
Теорема (Уильям Татт, англ. William Thomas Tutte, 1948 г.) 8.1. В произвольном
графе G = (V, E) совершенное паросочетание существует тогда и только тогда, когда для
любого подмножества вершин U
V подграф, построенный на оставшихся вершинах
V \ U (индуцированный подграф графа G), содержит не более |U | компонент связности с
нечётным числом вершин.
Таким образом, при поиске совершенного паросочетания в произвольном графе
сначала необходимо проверить его существование с помощью теоремы Татта. Затем, если
совершенное паросочетание в графе существует, найти его как максимальное
паросочетание в графе.
Однако, особое значение задача о поиске совершенного паросочетания имеет для
двудольных графов. Кроме того, теорема Татта является обобщением другой аналогичной
теоремы, использующейся при поиске совершенного паросочетания в двудольных графах.
Рассмотрим эту задачу в контексте двудольных графов.
8.2 Постановка задачи для двудольных графов
Формальная постановка задачи для двудольных графов не отличается от
постановки задачи для произвольного графа. Однако, такая задача будет иметь решение
ровно до тех пор, пока в двудольном графе
количество вершин в доле V
1
55
будет равно количеству вершин в доле V
2
: |V
1
| = |V
2
|. В ином же случае нас может
интересовать такое паросочетание, которое покрывает полностью лишь вершины какой-то
одной доли графа.
Определение 8.4. Пусть
– двудольный граф. Совершенным
паросочетанием из
в
является паросочетание, покрывающее вершины
(т.е.
включающее все вершины из него).
Задача о совершенных паросочетаниях в двудольных графах может быть
сформулирована весьма интересным образом: одна из постановок данной задачи
называется задачей о свадьбах. Приведём её формулировку ниже.
Пусть имеется конечное множество юношей, каждый из которых знаком с
некоторым подмножеством конечного множества девушек. В каком случае всех юношей
можно женить так, чтобы каждый женился на знакомой девушке?
В данном случае множество юношей и множество девушек – это соответственно
подмножества
и
двудольного графа
. Совершенным паросочетанием из
в
мы решим задачу о свадьбах, то есть каждому юноше подберём невесту. Если же нам
понадобится выдать замуж всех невест, то необходимо будет найти совершенное
паросочетание из
в
.
Совершенное паросочетание в двудольном графе также существует не всегда.
Достаточное условие существования решения задачи о совершенном паросочетании
формулирует теорема Холла, которая называется теоремой о свадьбах (англ. Hall’s
marriage theorem). Теорема Татта, приведённая выше, как-раз является обобщением
теоремы Холла на произвольные графы. Приведём теорему Холла ниже.
Теорема (Филипп Холл, англ. Philip Hall, 1935 г.) 8.2. Пусть
–
двудольный граф. Совершенное паросочетание из
в
существует тогда и только тогда,
когда вершины из любого подмножества
соединены по крайней мере с не меньшим
количеством вершин из
.
Иными словами, решение задачи о свадьбах существует тогда и только тогда, когда
у любых k юношей есть не менее k знакомых девушек.
Задача о совершенном паросочетании в двудольном графе имеет место в другой
интересной задаче – в задаче о назначениях.
8.3 Задача о назначениях
56
Задача о назначениях (англ. assignment problem) – это одна из известных задач
теории графов, а также теории исследования операций. Она имеет несколько вариантов
постановки. Приведём несколько.
Классическая постановка задачи звучит следующим образом. Есть n рабочих и n
заданий. Для каждого рабочего известны затраты на выполнение того или иного задания.
Каждый работник может быть назначен только на одно задание, и каждое задание может
выполняться только одним работником. Необходимо распределить задания между
работниками так, чтобы суммарные затраты на их выполнение были минимальными.
Постановка задачи в терминах теории графов звучит следующим образом. Дан
полный двудольный граф
с n вершинами, каждому его ребру приписан
некоторый вес. Необходимо найти совершенное паросочетание минимального веса.
Постановка задачи в матричном виде звучит следующим образом. Дана матрица A
размером n
n. Необходимо выбрать в матрице A n элементов так, чтобы в каждой строке
и в каждом столбце был выбран ровно один элемент, и при этом сумма выбранных
элементов была бы минимальной.
Все приведённые выше постановки являются эквивалентными. Кроме этого, в
описанной задаче количество работников n совпадает с количеством заданий m (и равно
n). Такая задача называется линейной задачей о назначениях. Встречаются и постановки
задачи, в которых n
m, и надо выбрать min(n,m) элементов. Однако, от таких
«прямоугольных» задач можно перейти к линейной «квадратной» задаче, просто добавив
дополнительно строки / столбцы с бесконечными / нулевыми значениями соответственно
(введение фиктивных работников / работ). Обычно, когда говорят о задаче о назначениях
без дополнительных условий, имеют в виду именно линейную задачу о назначениях.
Также отметим, что существует подобная задача на поиск максимального решения
вместо минимального. От одной к другой достаточно легко перейти: просто необходимо
умножить все веса на -1.
Рассмотрим пример поставленной задачи о назначениях. Пусть нам дана
следующая матрица:
57
В ней строки соответствуют работникам, столбцы – заданиям. Иными словами, на
пересечении третьей строки и второго столбца стоит значение, соответствующее затратам
третьего работника на выполнение второго задания. Такую матрицу можно
интерпретировать как матрицу смежности двудольного графа, и легко перейти к графовой
постановке задачи.
Определение 8.5. Пусть дан двудольный граф
, n – количество
вершин в доле V
1
, m – количество вершин в доле V
2
. Матрица смежности A двудольного
графа – это матрица n
m, которая имеет следующий вид:
Если граф G не взвешенный, то матрица состоит из нулей и единиц, и каждый элемент
матрицы вычисляется по формуле:
Если же граф взвешенный (каждому ребру графа поставлена в соответствие некоторая
величина – вес), то
, где
– вес ребра между вершиной
доли V
1
и вершиной
доли V
2
. Отметим, что часто вершины обеих долей нумеруются одинаково, с единицы
(вершина 1 доли V
1
, вершина 1 доли V
2
, и т.д.).
Итак, построим по заданной матрице двудольный граф. Вершины первой доли V
1
будут представлять работников, вершины второй доли V
2
будут представлять работы.
Построенный двудольный граф приведён на рисунке 8.2.
58
Рисунок 8.2 – Двудольный граф для задачи о назначениях
Линейную задачу о назначениях также можно свести к задаче о максимальном
потоке. Так как в данном случае двудольный граф является уже взвешенным, для её
решения необходимо будет применить алгоритм поиска максимального потока
минимальной стоимости. В остальном же сведение задачи к задаче о потоке в сети
происходит так же, как это было показано для задачи о максимальном паросочетании
(пункт 7.3).
Существуют и других алгоритмы решения задачи. Классический алгоритм решения
задачи о назначениях – это Венгерский алгоритм, который мы и рассмотрим дальше.
8.4 Венгерский алгоритм решения задачи о назначениях
Венгерский алгоритм (англ. Hungarian algorithm), или алгоритм Куна-Манкреса
(англ. Kuhn-Munkres algoritmn) – это один из классических алгоритмов, решающих задачу
о назначениях. Алгоритм имеет несколько интерпретаций, среди которых – графовая и
матричная. Часто встречается матричная интерпретация алгоритма, которую мы и
рассмотрим ниже. Начнём с описания алгоритма.
59
Алгоритм (матричная интерпретация Венгерского алгоритма)
Есть n рабочих и n заданий. Стоимости выполнения рабочими той или иной задачи
представлены в матрице A:
Ниже приводим алгоритм решения задачи в виде последовательности шагов.
1. В матрице найти в каждой строке минимальную стоимость и вычесть её из всех
элементов этой строки;
2. В полученной матрице найти в каждом столбце минимальную стоимость и вычесть
её из всех элементов этого столбца;
3. Пока в последней матрице не получено допустимое решение, выполнять:
3.1. В последней матрице провести минимальное число горизонтальных и
вертикальных прямых по строкам и столбцам, чтобы вычеркнуть в матрице все
нулевые элементы;
3.2. Найти наименьший невычеркнутый элемент и вычесть его из всех
невычеркнутых элементов и прибавить его к элементам, стоящим на
пересечении проведённых на шаге 3.1 прямых;
4. Решение найдено. Оптимальным назначениям соответствуют нулевые элементы
матрицы.
На шаге 3 алгоритма проверяется допустимость полученного решения. Решение
считается допустимым, если можно выбрать нулевые элементы в матрице так, чтобы в
каждой её строке и в каждом её столбце находился ровно один выбранный нулевой
элемент (то есть каждый рабочий назначен только на одну работу, и каждая работа
выполняется одним рабочим). Рассмотрим алгоритм на примере.
Пример 8.1.
Есть четыре работника и четыре задания. Стоимости выполнения работниками
заданий представлены в следующей матрице:
Пойдём по алгоритму.
На первом шаге находим минимальную стоимость в каждой строке, и вычитаем её
из всех элементов данной строки. Минимум в первой строке – 1, во второй – 7, в третьей –
60
4, в четвёртой – 5. Вычитаем эти значения из соответствующих строк. Получаем
следующую матрицу:
На втором шаге находим минимальную стоимость в каждом столбце, и вычитаем
её из соответствующего столбца. Минимум в первом столбце – 0, во втором – 0, в третьем
– 3, в четвёртом – 0. Вычитаем значения из соответствующих столбцов. Получаем
следующую матрицу:
Решение, которое сейчас имеется в матрице, нас не устраивает: работник 1 и
работник 3 могут быть назначены только на задачу 1 – других вариантов для них нет.
Такое назначение недопустимо. Продолжаем решение.
Выделяем в матрице минимальное количество строк и столбцов так, чтобы все
нулевые элементы стали выделенными (рисунок 8.3).
Рисунок 8.3 – Выделенные строки и столбцы
Наименьший невыделенный элемент – 1 (третья строка, второй столбец). Вычтем
его из всех невыделенных элементов, и прибавим к элементам, стоящим на пересечении
выделенных строк и столбцов (их два: элемент во второй строке и первом столбце, и
элемент в четвёртой строке и первом столбце). Получим следующую матрицу:
В полученной матрице допустимое решение существует (рисунок 8.4).
61
Рисунок 8.4 – Оптимальное назначение
Таким образом, оптимально назначить работника 1 на задачу 1, работника 2 на
задачу 3, работника 3 на задачу 2, работника 4 на задачу 4. Затраты на данное назначение
можно вычислить по исходной матрице A, они равны: 1 + 10 + 5 + 5 = 21 ед.
Алгоритм кажется понятным для ручного счёта. Однако, есть два вопроса, на
которые необходимо ответить перед программированием алгоритма:
1. Как на шаге 3 узнать, существует ли в полученной матрице допустимое решение, и как
найти его?
2. Как на шаге 3.1 найти оптимальное выделение строк и столбцов?
Для того, чтобы узнать, существует ли в полученной матрице A’ оптимальное
решение, необходимо построить по ней двудольный граф G’: доля V
1
графа так же будет
соответствовать рабочим, доля V
2
– работам. Дуга в графе G’ между вершинами v
i
V
1
и
v
j
V
2
будет существовать при условии, что на пересечении i-ой строки и j-ого столбца в
матрице стоит нуль. То есть, мы строим двудольных граф, рёбра которого соответствуют
нулевым элементам матрицы A’. Для построенного графа G’ с помощью алгоритма Куна
необходимо найти максимальное паросочетание. Если полученное максимальное
паросочетание является совершенным, то оптимальное назначение найдено – на него
указывают рёбра данного паросочетания. Если же оптимальное решение найдено пока не
было, переходим к шагу 3.1.
На шаге 3.1, для того, чтобы найти оптимальное выделение строк и столбцов,
необходимо выполнить следующие действия. Отметим в матрице A’ нули,
соответствующие рёбрам построенного максимального паросочетания в графе G’.
Назовём эти нули «красными». Затем пометим все строки, в которых нет «красных» нулей
(строки без назначений). Затем - пометим все столбцы с нулями в этих строках. Затем –
пометим все строки с «красными» нулями в этих столбцах. Продолжаем помечать строки
и столбцы до тех пор, пока помечаются новые столбцы. После этого выделяем все
отмеченные столбцы и все неотмеченные строки. Оптимальное выделение строк и
столбцов получено.
Теперь уточним алгоритм с учётом приведённых дополнений.
62
Алгоритм (уточнённая матричная интерпретация Венгерского алгоритма)
1. В матрице найти в каждой строке минимальную стоимость и вычесть её из всех
элементов этой строки;
2. В полученной матрице найти в каждом столбце минимальную стоимость и вычесть
её из всех элементов этого столбца;
3. По последней матрице построить двудольный граф G’. Рёбра графа G’
соответствуют нулевым элементам данной матрицы;
4. С помощью алгоритма Куна найти максимальное паросочетание M в графе G’;
5. В последней матрице отметить нули, соответствующие рёбрам паросочетания M,
красным цветом;
6. Если M является совершенным паросочетанием, перейти на шаг 10;
7. В последней матрице отметить все строки, в которых нет «красных» нулей.
Отметить все столбцы с нулями в этих строках. Отметить все строки с «красными»
нулями в этих столбцах;
8. Вычеркнуть в последней матрице все отмеченные столбцы и все неотмеченные
строки;
9. В последней матрице найти наименьший невычеркнутый элемент и вычесть его из
всех невычеркнутых элементов и прибавить его к элементам, стоящим на
пересечении проведённых на шаге 8 прямых. Перейти на шаг 3;
10. Решение найдено. Оптимальным назначениям соответствуют отмеченные красным
нулевые элементы последней матрицы.
Вновь рассмотрим пример 8.1, но более детально.
Пример 8.2.
Используем исходные данные из примера 8.1.
После первого шага получаем матрицу:
После второго шага получаем матрицу:
Строим по последней матрице двудольный граф. Рёбра графа соответствуют
нулевым элементам матрицы. С помощью алгоритма Куна найдём максимальное
паросочетание в построенном графе. Построенный граф изображён на рисунке 8.5,
найденное паросочетание выделено зелёным.
63
Рисунок 8.5 – Двудольный граф для матрицы после второго шага
Отмечаем в матрице «красные» нули – подчеркнём их. Отметим строки, в которых
нет красных нулей (строка 3). Отметим все столбцы с нулями в этих строках (столбец 1).
Отметим все строки с красными нулями в этих столбцах (строка 1). Результат приведён на
рисунке 8.6.
Рисунок 8.6 – Отмеченные строки и столбцы
Выделим все отмеченные столбцы и все неотмеченные строки (рисунок 8.3).
Находим минимальный невычеркнутый элемент, вычитаем его из всех невычеркнутых и
прибавляем его к элементам, находящимся на пересечении выделенных строк и столбцов.
Получаем матрицу:
Строим по полученной матрице двудольный граф. Ищем в нём максимальное
паросочетание (рисунок 8.7).
64
Рисунок 8.7 – Двудольный граф последней матрицы
Получились результаты, аналогичные уже представленным результатам в примере
4.1.
Венгерский алгоритм имеет под собой две основные идеи, на которые мы уже
успели посмотреть:
1. вычитание из всех элементов некоторой строки / столбца одного и того же числа
изменит стоимости, но не изменит оптимальное решение,
2. если есть решение нулевой стоимости, то оно оптимально.
Таким образом, алгоритм нацелен на поиск значений, которые необходимо вычесть
из строк / столбцов матрицы, чтобы получить нулевые решения.
Список литературы
1. С. Н. Олехник Старинные занимательные задачи / С. Н. Олехник, Ю. В.
Нестеренко, М. К. Потапов. – 2-е изд., стереотип. – М. : Дрофа, 2005. – 173, [3] с.
: ил. – (Познавательно! Занимательно!).
2. Андерсон, Джеймс А. Дискретная математика и комбинаторика. : Пер. с англ. –
М. : Издательский дом «Вильямс», 2004. – 960 с. : ил. – Парал. тит. англ.
3. Ф.А. Новиков Дискретная математика для программистов: Учебник для вузов. 3-
е изд. – СПб.: Питер, 2009. – 384 с.: ил. – (Серия «Учебник для вузов»).
4. Ф.А. Новиков Дискретная математика для программистов: Учебник для вузов. 2-
е изд. Стандарт третьего поколения. – СПб.: Питер, 2013. – 432 с.: ил.
5. Алексеев В. Е., Захарова Д. В. ТЕОРИЯ ГРАФОВ: Учебное пособие. – Нижний
Новгород: Нижегородский госуниверситет, 2017. – 119 с.
6. Г. Вагнер Основы исследования операций. Том 1.: Пер. с англ. – М.: Издательство
«Мир», 1972. – 336 с.
7. Йенсен П., Барнес Д. Потоковое программирование.: Пер. с англ. – М.: Радио и
связь, 1984. – 392 с., ил.
8. Романовский И.В. Дискретный анализ: Учебное пособие для студентов,
специализирующихся по прикладной математике и информатике. – 4-е изд.,
испр. и доп. – СПб.: Невский Диалект, БХВ-Петербург, 2008. – 336 с.: ил.
9. Р. Хаггарти Дискретная математика для программистов. – М.: Техносфера, 2003.
– 320 с.
10. Таха, Хэмди А. Введение в исследование операций, 7-е изд.: Пер. с англ. – М.:
Издательский дом «Вильямс», 2007. – 912 с.: ил. – Парал. тит. англ.
11. Карпов Д. В. Теория графов. – 555 с.
12. Стивенс Р. Алгоритмы. Теория и практическое применение: Пер. с англ. - М.: Э.
2016. 544 с.
13. Смирнов С.Н., Галкина В.А. Оптимизационные задачи на графах: учебно-
методическое пособие, - М.: Гелиос АРВ. 2012. 368 с.
14. Липский В. Комбинаторика для программистов. - М.: Мир.1988. 200 с.
15. Edmond’s Matching [Электронный ресурс]. Доступно на сайте:
https://ru.scribd.com/document/58609549/Edmond-s-Matching
16. Паросочетания [Электронный ресурс]. Доступно на сайте:
https://algorithmica.org/ru/matching
66
17. Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе
[Электронный ресурс]. Доступно на сайте:
https://e-maxx.ru/algo/kuhn_matching
18. Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных
графах [Электронный ресурс]. Доступно на сайте:
https://e-maxx.ru/algo/matching_edmonds
19. Задача о назначениях. Венгерский алгоритм решения задачи о назначениях
[Электронный ресурс]. Доступно на сайте:
https://e-maxx.ru/algo/assignment_hungary
